159993 - 미로 탈출

정보

• 문제 보기: 159993 - 미로 탈출
• 소요 시간: 33분 12초
• 풀이 언어: java
• 체감 난이도: 2️⃣~3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

bfs

풀이 코드

정보

• 메모리: 91800 KB
• 시간: 15 ms

import java.util.*;

class Solution {
    int[] dy = {-1, 0, 0, 1};
    int[] dx = {0, -1, 1, 0};
    int n, m;
    
    public int solution(String[] maps) {
        int n = maps.length;
        int m = maps[0].length();
        
        int sy = -1, sx = -1;
        int ly = -1, lx = -1;
        int ey = -1, ex = -1;
        int[][] map = new int[n][m];
        
        // init map
        for (int i = 0; i < n; ++i) {
            String[] data = maps[i].split("");
            for (int j = 0; j < m; ++j) {
                String d = data[j];
                if (d.equals("S")) {
                    sy = i;
                    sx = j;
                }
                else if (d.equals("E")) {
                    ey = i;
                    ex = j;
                }
                else if (d.equals("L")) {
                    ly = i;
                    lx = j;
                }
                else if (d.equals("X")) {
                    map[i][j] = 1;
                }
                else {
                    // 0은 기본 마킹됨
                }
            }
        }
        
        /* bfs */
        Deque<int[]> dq = new ArrayDeque<>();
        
        boolean[][] visited = new boolean[n][m];
        visited[sy][sx] = true;
        
        int cntToLever = -1;
        int cntToEnd = -1;
        
        // bfs1: 레버 도착
        dq.add(new int[]{sy, sx, 0}); // start pos
        while (!dq.isEmpty()) {
            int[] pos = dq.poll();
            int y = pos[0];
            int x = pos[1];
            int c = pos[2];
            if (y == ly && x == lx) {
                cntToLever = c;
                break;
            }
            for (int d = 0; d < 4; ++d) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < n &&
                    0 <= nx && nx < m &&
                    map[ny][nx] == 0 &&
                    !visited[ny][nx])
                {
                    visited[ny][nx] = true;
                    dq.add(new int[]{ny, nx, c+1});
                }
            }
        }
        
        if (cntToLever == -1) return -1;
        
        // bfs2: 출구칸 도착
        dq = new ArrayDeque<>(); // **IMPORTANT**
        dq.add(new int[]{ly, lx, cntToLever}); // lever pos
        for (boolean[] line : visited) // init visited
            Arrays.fill(line, false);
        visited[ly][lx] = true;
        
        while (!dq.isEmpty()) {
            int[] pos = dq.poll();
            int y = pos[0];
            int x = pos[1];
            int c = pos[2];
            if (y == ey && x == ex) {
                cntToEnd = c;
                break;
            }
            for (int d = 0; d < 4; ++d) {
                int ny = y + dy[d];
                int nx = x + dx[d];
                if (0 <= ny && ny < n &&
                    0 <= nx && nx < m &&
                    map[ny][nx] == 0 &&
                    !visited[ny][nx]
                   )
                {
                    visited[ny][nx] = true;
                    dq.add(new int[]{ny, nx, c+1});
                }
            }
        }
        
        return cntToEnd;
    }
}

풀이 해설

다음의 2가지 구간을 나눠서 2번 BFS를 수행하면 된다.

1. 시작(S) ~ 레버(L)
2. 레버(L) ~ 끝(E)

큐 재탕 실수 주의

BFS 큐를 재탕하다가 new 처리 까먹으면 꼬여서 WA 받을 수 있다.
new를 깜빡하는 실수를 원천 차단하기 위해 아예 BFS마다 별도의 큐를 생성하는 쪽을 추천한다.

실수하기 쉬운 부분

// bfs2: 출구칸 도착
dq = new ArrayDeque<>(); // **IMPORTANT**
dq.add(new int[]{ly, lx, cntToLever}); // lever pos
for (boolean[] line : visited) // init visited
    Arrays.fill(line, false);
visited[ly][lx] = true;

while (!dq.isEmpty()) {
    int[] pos = dq.poll();
    ...

메모

• 레버(L) ~ 끝(E) 으로 bfs 수행할때 탐색 첫 시작 노드의 카운터로 0이 아닌 cntToLever를 넣어주는게 마지막 return 문에서 더 깔끔하게 떨어짐